﻿/*
* @autor: hectorea
* @date: 24/07/12
* @programing interview 6
*/

using System;
using System.Diagnostics;
using System.Linq;

namespace FindRepeatedLetters
{
    /// <summary>
    /// Programing Interview 6: Write a program to find the repeated letters in a given string by taking number of repetitions as an input.
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch sw1 = new Stopwatch();
            //sw1.Start();
            //ASCIIBasedSolution("ABDCFNABFASDFJDL", 3);
            //sw1.Stop();
            //Console.WriteLine("Elapsed Time: {0}", sw1.ElapsedTicks);

            //sw1.Start();
            //ASCIIBasedSolutionOptimized("ABDCFNABFASDFJDL", 3);
            //sw1.Stop();
            //Console.WriteLine("Elapsed Time: {0}", sw1.ElapsedTicks);

            //sw1.Start();
            //ASCIIBasedSolution("ABDCFNABFASDFJDL", 3);
            //sw1.Stop();
            //Console.WriteLine("Elapsed Time: {0}", sw1.ElapsedTicks);

            sw1.Start();
            ASCIIBasedSolution("ABDCFNABFASDFJDL", 3);
            sw1.Stop();

            Console.WriteLine("Elapsed Time: {0}", sw1.ElapsedTicks);
            Console.ReadLine();
        }

        /// <summary>
        /// This aproach is good and will work if the input string are within the chars represented in the ASCII Table
        /// 
        /// I need to know if the input string only will be alphabet chars; if that is the case, this approach won't work.
        /// 
        /// Complexity: O(2n)
        /// </summary>
        /// <param name="input">Input String (Any char in ASCII Code)</param>
        /// <param name="repetitions">Number of repetitions</param>
        public static void ASCIIBasedSolution(string input, int repetitions)
        {
            if (input.Length <= 0)
                throw new ArgumentNullException("The string cannot be null or empty");

            //I'm assuming that the string could be any char represented in the ASCII Table
            int[] alphabet = new int[256];

            //Store every char and increment in one every repetition
            for (int i = 0; i < input.Length; i++)
                alphabet[input[i]]++;

            //Loop to know which char meet the repetitions required
            for (int i = 0; i < alphabet.Length; i++)
            {
                if (alphabet[i] == repetitions)
                    Console.WriteLine(" {0} ", (char)i);
            }
        }

        /// <summary>
        /// Oprimized version assuming that our input string only will be letters
        /// </summary>
        /// <param name="input">Input String (We assume that we'll receive letter of the english alphabet)</param>
        /// <param name="repetitions"></param>
        public static void ASCIIBasedSolutionOptimized(string input, int repetitions)
        {
            if (input.Length <= 0)
                throw new ArgumentNullException("The string cannot be null or empty");

            input = input.ToUpper();

            //I'm assuming that the string should be only letters of the english alphabet
            int[] alphabet = new int[25];

            //Store every char and increment in one every repetition
            for (int i = 0; i < input.Length; i++)
                alphabet[input[i] - 65]++;

            //Loop to know which char meet the repetitions required
            for (int i = 0; i < alphabet.Length; i++)
            {
                if (alphabet[i] == repetitions)
                    Console.WriteLine(" {0} ", (char)(i + 65));
            }
        }

        /// <summary>
        /// This approach perfome something like a BubbleSort. I use two loops to iterate through the string.  
        /// One to check the current char and the another
        /// to check how many times is repeated in the string.
        /// 
        /// Complexity: O(n2)
        /// </summary>
        /// <param name="input"></param>
        /// <param name="repetitions"></param>
        public static void FindRepeatedChars(string input, int repetitions)
        {
            int current = 0;
            //Current position
            for (int i = 0; i < input.Length; i++)
            {
                //how many times is repeated?
                for (int j = i; j < input.Length; j++)
                {
                    //Are equals?
                    if (input[i] == input[j])
                        current++;
                }

                if (current == repetitions)
                    Console.WriteLine(input[i]);

                current = 0;
            }
        }

        /// <summary>
        /// Just another solutions implementing Linq
        /// </summary>
        /// <param name="input">Input String</param>
        /// <param name="repetitions">Number of repetitions</param>
        public static void LinqSolution(string input, int repetitions)
        {
            char[] inputArray = input.ToCharArray();
            var duplicates = inputArray.GroupBy(x => x)
                .Where(x => x.Count() >= repetitions)
                .Select(x => x.Key);

            foreach (var item in duplicates)
                Console.WriteLine(item);
        }
    }
}

